package com.sjf.day02.hashtable;

import cn.hutool.core.bean.BeanUtil;
import com.mysql.jdbc.StringUtils;

import java.util.Scanner;

/**
 * 哈希表
 *
 * @author <huangtang>
 * @since 2021/12/31 14:49
 **/
public class HashTabDemo {

    public static void main(String[] args) {

        //创建哈希表
        HashTab hashTab = new HashTab(7);
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while(true){

            System.out.print("add(添加节点) \t");
            System.out.print("list(显示所有节点) \t");
            System.out.print("get(获取节点) \t");
            System.out.print("del(删除节点) \t");
            System.out.println("quit(退出程序) \t");

            key = scanner.next();
            switch (key){
                case "add":
                    System.out.print("输入id：");
                    int id = scanner.nextInt();
                    System.out.print("输入名字：");
                    String name = scanner.next();
                    System.out.println("选择有序插入还是无序插入 1:有序插入 2:无序插入");
                    int is = scanner.nextInt();
                    if(is == 1){
                        hashTab.addById(new Empty(id,name));
                    }else if(is == 2){
                        hashTab.add(new Empty(id,name));
                    }
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "get":
                    System.out.println("请输入id：");
                    hashTab.getById(scanner.nextInt());
                    break;
                case "del":
                    System.out.println("请输入id：");
                    hashTab.delById(scanner.nextInt());
                    break;
                case "quit":
                    scanner.close();
                    break;
                default:
                    break;
            }
        }

    }

}

/**
 * 哈希表,管理多条链表
 */
class HashTab{
    private int size; //数组大小
   private EmptyLinkedList[] emptyLinkedListArr;

    /**
     * 初始化哈市表
     * @param size1 数组大小
     */
    public HashTab(int size1) {
        this.size = size1;
        this.emptyLinkedListArr = new EmptyLinkedList[size];
        for (int i = 0; i < size1; i++) {
            emptyLinkedListArr[i] = new EmptyLinkedList();
        }
    }


    //添加
    public void add(Empty empty){
        //添加到哪条链表
        int empLinkedListNo = hash(empty.id);
        //添加到对应的链表中
        emptyLinkedListArr[empLinkedListNo].add(empty);
    }

    //按id递增的方式添加到链表中
    public void addById(Empty empty){
        int id = hash(empty.id);
        //添加到对应的链表中
        emptyLinkedListArr[id].addById(empty);
    }
    //遍历哈希表
    public void list(){
        for (int i = 0; i < emptyLinkedListArr.length; i++) {
            emptyLinkedListArr[i].list(i);
        }
    }

    public void getById(int id){
        Empty emp = emptyLinkedListArr[hash(id)].getById(id);
        if(emp!=null){
            //找到
            System.out.println("在第"+hash(id)+"条链表找到该节点"+emp.id+emp.name);
        }else{
            //没找到
            System.out.println("不存在该节点");
        }
    }
    public void delById(int id){
        emptyLinkedListArr[hash(id)].delById(id);
        System.out.printf("第 %d 条链表删除节点id= %d",hash(id),id);
    }

    //编写散列函数，添加的节点到哪个链表上
    private int hash(int id){
        return id % size;
    }
}

/**
 * 员工实体类
 */
class Empty{
    public int id;
    public String name;
    public Empty next; //默认为空

    public Empty(int id, String name) {
        this.id = id;
        this.name = name;
    }

}

/**
 * 链表
 */
class EmptyLinkedList{
    public Empty head; //头指针

    //添加
    public void add(Empty empty){
        //如果是添加第一个节点
        if(head == null){
            head = empty;
            return;
        }
        //否则遍历到链表尾部
        Empty tmp = head;
        while(true){
            if(tmp.next==null){
                break;
            }
            tmp = tmp.next;
        }
        tmp.next = empty; //直接加入即可
    }

    //递增添加
    public void addById(Empty empty){
        //如果是添加第一个节点
        if(head == null){
            head = empty;
            return; //链表为空时，插入后直接返回
        }
        Empty tmp = head;
        if(empty.id < head.id){
            //插入位置在头节点
            head = empty;
            empty.next = tmp;
            return; //插入后直接return
        }
        while(true){
            if(tmp.next == null){
                tmp.next = empty;
                //到达尾部
                break;
            }
            if(empty.id<tmp.next.id){
                //找到插入的位置
                empty.next = tmp.next;
                tmp.next = empty;
                break;
            }
            tmp = tmp.next;
        }
        //empty.next = tmp.next;
        //tmp.next = empty; //直接加入即可
    }

    //遍历链表
    public void list(int no){
        if(head == null){
            System.out.println("第"+no+"条链表为空");
            return;
        }
        Empty temp = head;
        System.out.print("第"+no+"条链表信息为");
        while(true){
            System.out.print(temp.id+"\t"+temp.name);
            if(temp.next == null){
                break;
            }
            temp = temp.next;
            System.out.print("\t-->\t");
        }
        System.out.println();
    }

    //获取链表上的某个节点
    public Empty getById(int id){
        if(head == null){
            System.out.println("链表为空");
            return null;
        }
        Empty temp = head;
        while(true){
            if(temp == null){
                System.out.println("不存在该节点信息");
                break;
            }
            if(temp.id == id){
                //找到直接返回
                return temp;
            }
            temp = temp.next; //向后遍历
        }
        return null;
    }

    //删除链表上的某个节点
    public void delById(int id){
        if(head == null){
            System.out.println("链表为空");
            return;
        }
        Empty temp = head;
        while(true){
            if(temp.id == id){
                //删除的节点是头节点
                head = temp.next;
                break;
            }
            if(temp.next == null) {
                //到达链表尾部了
                System.out.println("该节点不存在");
                break;
            }
            if(temp.next.id == id){
                //找到要删除的节点了，此时处于前一个位置
                temp.next = temp.next.next;
                break;
            }
            //链表向后遍历
            temp = temp.next;
        }
    }
}
